package com.leetcode.partition8;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/11/13 10:33
 */
public class LC773滑动谜题 {

    private static final int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public static int slidingPuzzle(int[][] board) {
        return bfs(board);
    }

    public static void main(String[] args) {
        int[][] board = {{4, 1, 2}, {5, 0, 3}};
        System.out.println(slidingPuzzle(board));
    }

    private static int bfs(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                sb.append(board[i][j]);
            }
        }
        String startStr = sb.toString();
        //双向bfs
        LinkedList<String> queue1 = new LinkedList<>(), queue2 = new LinkedList<>();
        Map<String, Integer> dis1 = new HashMap<>(), dis2 = new HashMap<>();
        queue1.addLast(startStr);
        dis1.put(startStr, 0);
        queue2.addLast("123450");
        dis2.put("123450", 0);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            int ans = queue1.size() >= queue2.size() ? search(queue2, dis2, dis1, startStr) : search(queue1, dis1, dis2, "123450");
            if (ans != -1) return ans;
        }
        return -1;
    }

    private static int search(LinkedList<String> queue, Map<String, Integer> disMap, Map<String, Integer> opposite, String target) {
        String cur = queue.poll();
        int dis = disMap.get(cur);
        if (target.equals(cur)) return dis;
        //得到当前状态空格的行和列，字符串始终是2*3
        int row = 0, col = 0, curIndex = 0;
        for (int i = 0; i < cur.length(); i++) {
            if (cur.charAt(i) == '0') {
                row = i / 3;
                col = i % 3;
                curIndex = i;
                break;
            }
        }
        //空格位置和周边元素进行互换
        for (int[] dir : dirs) {
            int nextRow = dir[0] + row, nextCol = dir[1] + col;
            if (nextRow < 0 || nextRow >= 2 || nextCol < 0 || nextCol >= 3) continue;
            //得到合法的邻节点并转化为一维索引
            int index = nextRow * 3 + nextCol;
            //交换curIndex和index的字符，得到新的状态
            char[] curArray = cur.toCharArray();
            char temp = curArray[curIndex];
            curArray[curIndex] = curArray[index];
            curArray[index] = temp;
            String next = new String(curArray);
            //要求新状态没有重复过，如果没有重复，就将新交换后的状态加入到队列
            if (disMap.containsKey(next)) continue;
            //如果在另一个方向出现过，直接返回总距离
            if (opposite.containsKey(next)) {
                return dis + 1 + opposite.get(next);
            }
            queue.addLast(next);
            disMap.put(next, dis + 1);
        }
        return -1;
    }
}
